// Linked List class
// (c) jimon game studio
// Copyright (C) 2002-2007 Nikolaus Gebhardt

#ifndef JEH_JELIST
#define JEH_JELIST

#include "jeTypes.h"
#include "jeMemory.h"

namespace je
{

	//! Double linked jeList template.
	template <class T>
	class jeList
	{
	//private:
	public:

		//! List element node with pointer to previous and next element in the jeList.
		struct SKListNode
		{
			SKListNode() : Next(0), Prev(0) {};

			SKListNode* Next;
			SKListNode* Prev;
			T Element;
		};

	public:
		class ConstIterator;

		//! List iterator.
		class Iterator
		{
		public:
			Iterator() : Current(0) {}

			Iterator& operator ++()    { Current = Current->Next; return *this; }
			Iterator& operator --()    { Current = Current->Prev; return *this; }
			Iterator  operator ++(s32) { Iterator tmp = *this; Current = Current->Next; return tmp; }
			Iterator  operator --(s32) { Iterator tmp = *this; Current = Current->Prev; return tmp; }

			Iterator& operator +=(s32 num)
			{
				if(num > 0)
				{
					while (num-- && this->Current != 0) ++(*this);
				}
				else
				{
					while(num++ && this->Current != 0) --(*this);
				}
				return *this;
			}

			Iterator  operator + (s32 num) const { Iterator tmp = *this; return tmp += num; }
			Iterator& operator -=(s32 num) const { return (*this)+=(-num); }
			Iterator  operator - (s32 num) const { return (*this)+ (-num); }

			u1 operator ==(const Iterator&      other) const { return Current == other.Current; }
			u1 operator !=(const Iterator&      other) const { return Current != other.Current; }
			u1 operator ==(const ConstIterator& other) const { return Current == other.Current; }
			u1 operator !=(const ConstIterator& other) const { return Current != other.Current; }

			#if defined (_MSC_VER) && (_MSC_VER < 1300)
				#pragma warning(disable:4284) // infix notation problem when using iterator operator ->
			#endif 

			T & operator * () { return Current->Element;  }
			T * operator ->() { return &Current->Element; }

			SKListNode * GetCurrent()
			{
				return Current;
			}

		private:
			Iterator(SKListNode* begin) : Current(begin) {}

			SKListNode* Current;

			friend class jeList<T>;
		};

		class ConstIterator
		{
		public:

			ConstIterator() : Current(0) {}

			ConstIterator& operator ++()    { Current = Current->Next; return *this; }
			ConstIterator& operator --()    { Current = Current->Prev; return *this; }
			ConstIterator  operator ++(s32) { ConstIterator tmp = *this; Current = Current->Next; return tmp; }
			ConstIterator  operator --(s32) { ConstIterator tmp = *this; Current = Current->Prev; return tmp; }

			ConstIterator& operator +=(s32 num)
			{
				if(num > 0)
				{
					while(num-- && this->Current != 0) ++(*this);
				}
				else
				{
					while(num++ && this->Current != 0) --(*this);
				}
				return *this;
			}

			ConstIterator  operator + (s32 num) const { ConstIterator tmp = *this; return tmp += num; }
			ConstIterator& operator -=(s32 num) const { return (*this)+=(-num); }
			ConstIterator  operator - (s32 num) const { return (*this)+ (-num); }

			u1 operator ==(const ConstIterator& other) const { return Current == other.Current; }
			u1 operator !=(const ConstIterator& other) const { return Current != other.Current; }
			u1 operator ==(const Iterator&      other) const { return Current == other.Current; }
			u1 operator !=(const Iterator&      other) const { return Current != other.Current; }

			const T & operator * () { return Current->Element; }
			const T * operator ->() { return &Current->Element; }

			ConstIterator & operator =(const Iterator & iterator) { Current = iterator.Current; return *this; }

		private:
			ConstIterator(SKListNode* begin) : Current(begin) {}

			SKListNode* Current;

			friend class Iterator;
			friend class jeList<T>;
		};

		//! constructor
		jeList()
			: First(0), Last(0), Size(0) {}


		//! copy constructor
		jeList(const jeList<T>& other) : First(0), Last(0), Size(0)
		{
			*this = other;
		}


		//! destructor
		~jeList()
		{
			clear();
		}


		//! Assignment operator
		void operator=(const jeList<T>& other)
		{
			if(&other == this)
			{
				return;
			}

			clear();

			SKListNode* node = other.First;
			while(node)
			{
				push_back(node->Element);
				node = node->Next;
			}
		}



		//! Returns amount of elements in jeList.
		//! \return Returns amount of elements in the jeList.
		u32 getSize() const
		{
			return Size;
		}



		//! Clears the jeList, deletes all elements in the jeList. All existing
		//! iterators of this jeList will be invalid.
		void clear()
		{
			while(First)
			{
				SKListNode * next = First->Next;
				JEDELETE(First)
				First = next;
			}

			//First = 0; handled by loop
			Last = 0;
			Size = 0;
		}



		//! Returns ture if the jeList is empty.
		//! \return Returns true if the jeList is empty and false if not.
		u1 empty() const
		{
			return (First == 0);
		}



		//! Adds an element at the end of the jeList.
		//! \param element: Element to add to the jeList.
		void push_back(const T& element)
		{
			SKListNode* node;
			JENEW(node,SKListNode)
			node->Element = element;

			++Size;

			if (First == 0)
				First = node;

			node->Prev = Last;

			if (Last != 0)
				Last->Next = node;

			Last = node;
		}


		//! Adds an element at the begin of the jeList.
		//! \param element: Element to add to the jeList.
		void push_front(const T& element)
		{
			SKListNode* node;
			JENEW(node,SKListNode)
			node->Element = element;

			++Size;

			if (First == 0)
			{
				Last = node;
				First = node;
			}
			else
			{
				node->Next = First;
				First->Prev = node;
				First = node;
			}
		}


		//! Gets begin node.
		//! \return Returns a jeList iterator pointing to the begin of the jeList.
		Iterator begin()
		{
			return Iterator(First);
		}


		//! Gets begin node.
		//! \return Returns a jeList iterator pointing to the begin of the jeList.
		ConstIterator begin() const
		{
			return ConstIterator(First);
		}


		//! Gets end node.
		//! \return Returns a jeList iterator pointing to null.
		Iterator end()
		{
			return Iterator(0);
		}


		//! Gets end node.
		//! \return Returns a jeList iterator pointing to null.
		ConstIterator end() const
		{
			return ConstIterator(0);
		}


		//! Gets last element.
		//! \return Returns a jeList iterator pointing to the end of the jeList.
		Iterator getLast()
		{
			return Iterator(Last);
		}


		//! Gets last element.
		//! \return Returns a jeList iterator pointing to the end of the jeList.
		ConstIterator getLast() const
		{
			return ConstIterator(Last);
		}


		//! Inserts an element after an element.
		//! \param it: Iterator pointing to element after which the new element
		//! should be inserted.
		//! \param element: The new element to be inserted into the jeList.
		void insert_after(const Iterator& it, const T& element)
		{
			SKListNode* node;
			JENEW(node,SKListNode)
			node->Element = element;

			node->Next = it.Current->Next;

			if (it.Current->Next)
				it.Current->Next->Prev = node;

			node->Prev = it.Current;
			it.Current->Next = node;
			++Size;

			if (it.Current == Last)
				Last = node;
		}


		//! Inserts an element before an element.
		//! \param it: Iterator pointing to element before which the new element
		//! should be inserted.
		//! \param element: The new element to be inserted into the jeList.
		void insert_before(const Iterator& it, const T& element)
		{
			SKListNode* node;
			JENEW(node,SKListNode)
			node->Element = element;

			node->Prev = it.Current->Prev;

			if (it.Current->Prev)
				it.Current->Prev->Next = node;

			node->Next = it.Current;
			it.Current->Prev = node;
			++Size;

			if (it.Current == First)
				First = node;
		}


		//! Erases an element
		//! \param it: Iterator pointing to the element which shall be erased.
		//! \return Returns iterator pointing to next element.
		Iterator erase(Iterator& it)
		{
			// suggest changing this to a const Iterator& and
			// working around line: it.Current = 0 (possibly with a mutable, or just let it be garbage?)

			Iterator returnIterator(it);
			++returnIterator;

			if(it.Current == First)
			{
				First = it.Current->Next;
			}
			else
			{
				it.Current->Prev->Next = it.Current->Next;
			}

			if(it.Current == Last)
			{
				Last = it.Current->Prev;
			}
			else
			{
				it.Current->Next->Prev = it.Current->Prev;
			}

			JEDELETE(it.Current)
			it.Current = 0;
			--Size;

			return returnIterator;
		}

	private:

		SKListNode* First;
		SKListNode* Last;
		u32 Size;

	};
};

#endif
